package leetcode_61_80;

public class searchMatrix_74 {
    /**
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     *
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        /**
         * 想法是当作常规的二分查找，对坐标进行转化操作
         */
        int row=matrix.length,col=matrix[0].length;
        int left=0,right=row*col-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            int left_row=left/col,left_col=left%col,          //计算出相应的位置坐标
                    right_row=right/col,right_col=right%col,
                    mid_row=mid/col,mid_col=mid%col;
            if(matrix[mid_row][mid_col]< target ){
                left=mid+1;
            }else if(matrix[mid_row][mid_col]> target)
                right=mid-1;
            else
                return true;
        }
        return false;
    }
}
